package cn.wit.test;

import org.junit.Test;

/**
 * 公约数测试
 * 
 * @author 16604
 *
 */
public class DemoCommonDivisor {
	public static void main(String[] args) {
		int a = 12;
		int b = 78;

		// 辗转相除法
		tossAndTurnDivision(a, b);

		// 相减法
		subtracting(a, b);

		// 穷举法
		bruteForce(a, b);
	}

	// 辗转相除法
	@Test
	public static void tossAndTurnDivision(int a, int b) {

		int c = 0;
		while (true) {
			c = a % b;

			if (c == 0) {
				if (b == 1)
					System.out.println("沒有");
				else {
					System.out.println("辗转相除求得最大公约：" + b);
				}
				break;
			}
			// 归一
			a = b;
			b = c;
		}

	}

	// 相减法
	@Test
	public static void subtracting(int a, int b) {

		while (true) {
			if (a == b) {
				if (a == 1)
					System.out.println("沒有");
				else {
					System.out.println("相减法求得最大公约：" + a);
				}
				break;
			}
			if (a > b) {
				a = a - b;
			}
			if (a < b) {
				b = b - a;
			}
		}
	}

	// 穷举法
	@Test
	public static void bruteForce(int a, int b) {

		int min = (a < b) ? a : b; // 找出a，b中小的那位数

		for (int i = min; i >= 1; i--) {
			if (a % i == 0 && b % i == 0) {
				if (i == 1)
					System.out.println("沒有");
				else {
					System.out.println("穷举求得最大公约：" + i);
					break;
				}
			}
		}
	}

}
